package com.heyqing.backtrack;

import java.util.Scanner;

/**
 * ClassName:Queen
 * Package:com.heyqing.backtrack
 * Description:
 *
 * @Date:2024/6/21
 * @Author:Heyqing
 */

public class Queen {
    //皇后数量
    private int number;
    // 存储每一行皇后的列位置
    private int[] queens;
    //标志
    private boolean flag = false;

    public Queen(){
        Scanner sc = new Scanner(System.in);
        System.out.print("请输入皇后数量：");
        number = sc.nextInt();
        queens = new int[number];
        sc.close();
    }
    public void solve(){
        placeQueen(0);
    }
    // 尝试在第row行放置皇后
    private void placeQueen(int row) {
        if (row == number) {
            // 所有行都成功放置了皇后
            if (!flag) {
                printSolution();
                flag = true; // 标记已经找到解决方案
            }
            return;
        }
        for (int col = 0; col < number && !flag; col++) {
            if (isSafe(row, col)) {
                queens[row] = col; // 在(row, col)位置放置皇后
                placeQueen(row + 1); // 递归地放置下一行的皇后
                queens[row] = 0; // 回溯，移除当前行的皇后
            }
        }
    }
    // 检查在(row, col)位置放置皇后是否安全
    private boolean isSafe(int row, int col) {
        // 检查列上是否有皇后互相攻击
        for (int i = 0; i < row; i++) {
            if (queens[i] == col) {
                return false;
            }
        }
        // 检查左上对角线上是否有皇后互相攻击
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (queens[i] == j) {
                return false;
            }
        }
        // 检查右上对角线上是否有皇后互相攻击
        for (int i = row - 1, j = col + 1; i >= 0 && j < number; i--, j++) {
            if (queens[i] == j) {
                return false;
            }
        }
        // 如果没有皇后互相攻击，则该位置是安全的
        return true;
    }
    // 打印一种解决方案
    private void printSolution() {
        printNum();
        for (int i = 0; i < number; i++) {
            for (int j = 0; j < number; j++) {
                if (queens[i] == j) {
                    System.out.print("Q ");
                } else {
                    System.out.print(". ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    private void printNum() {
        System.out.print("Queen:");
        for (int i = 0; i < number; i++) {
            System.out.print("\t(" + (i+1) + "," + (queens[i]+1) + ")");
        }
        System.out.println();
    }
}

